package chromosomes;

import java.util.ArrayList;
import java.util.Random;

import logic.TreeBin;

/**
 * class Geneticos
 * 
 * @author Marco Gallardo Casu
 * @author Miguel Cisneros Rojas
 * 
 */
public class GeneticAlgorithm {

	private int population;
	private double crossover;
	private double mutation;
	private boolean elitism;

	private ArrayList<Chromosome> chromosomes;
	private TypeSelection typeSelection;

	// Roulette
	private static int n; // N to reproduction
	private static int x; // X to keep (elitism)
	// Torunament
	private static int k; // Iterations of tournament
	private static int z = 3; // Z elements for mini-tournament
	// Global fitness
	private static double totalFitness;

	public GeneticAlgorithm(int population, double crossover, double mutation,
			TypeSelection typeSelection, boolean elitism) {
		this.population = population;
		this.crossover = crossover;
		this.mutation = mutation;
		this.elitism = elitism;
		this.chromosomes = generateRandomPopulation();
		this.typeSelection = typeSelection;
		if (elitism) {
			GeneticAlgorithm.x = population / 100;

		} else {
			GeneticAlgorithm.x = 0;
		}
		GeneticAlgorithm.n = population - x;
		GeneticAlgorithm.k = population - x;
	}

	public void cycle() {
		switch (typeSelection) {
		case RANKING:
			updateProbabilitiesRanking();
			break;
		case STOCHASTIC_UNIVERSAL:
			updateProbabilitiesStochastic();
			break;
		default:
			updateProbabilities();
			break;
		}
		if (elitism) {
			ArrayList<Chromosome> list = new ArrayList<Chromosome>(x);
			for (int i = 0; i < x; i++) {
				list.add(chromosomes.remove(0));
			}
			reproductionElite(list);
		}
		reproduction(selection());
	}

	public double getAverageGen() {
		double average = 0;

		for (Chromosome c : chromosomes) {
			average += c.getFitness();
		}

		average /= chromosomes.size();
		return average;
	}

	public Chromosome getBest() {
		return (Chromosome) chromosomes.get(0).clone();
	}

	public double getBestFitness() {
		return chromosomes.get(0).getFitness();
	}

	private void add(ArrayList<Chromosome> list, Chromosome chromosome) {
		chromosome.getTree().update();
		chromosome.evaluate();
		totalFitness += chromosome.getFitness();
		if (list.isEmpty()) {
			list.add(chromosome);
		} else {
			list.add(binarySearch(list, chromosome.getFitness()), chromosome);
		}
	}

	private void add(ArrayList<Chromosome> list, Chromosome[] childs) {
		for (Chromosome child : childs) {
			if (child != null) {
				add(list, child);
			}
		}
	}

	private int binarySearch(ArrayList<Chromosome> list, double aptitud) {
		return binarySearch(list, 0, list.size() - 1, aptitud);
	}

	private int binarySearch(ArrayList<Chromosome> list, int s, int e,
			double fitness) {
		if (s > e) {
			return s;
		}
		int medium = (s + e) / 2;
		double mediumFitness = list.get(medium).getFitness();
		if (mediumFitness == fitness) {
			return medium;
		} else if (mediumFitness > fitness) {
			return binarySearch(list, medium + 1, e, fitness);
		} else {
			return binarySearch(list, s, medium - 1, fitness);
		}
	}

	private int binarySearch2(ArrayList<Chromosome> list, double p) {
		return binarySearch2(list, 0, list.size() - 1, p);
	}

	private int binarySearch2(ArrayList<Chromosome> list, int s, int e, double p) {
		if (s > e) {
			return s;
		}
		int medium = (s + e) / 2;
		double pMedium = list.get(medium).getpAccumulated();
		if (pMedium == p) {
			return medium;
		} else if (pMedium > p) {
			return binarySearch2(list, s, medium - 1, p);
		} else {
			return binarySearch2(list, medium + 1, e, p);
		}
	}

	private void crossover(Chromosome[] c) {
		Random r = new Random();
		if (r.nextDouble() < crossover) {
			int numNodes = Math.min(c[0].getTree().getNumNodes(), c[1]
					.getTree().getNumNodes());
			int cN = r.nextInt(numNodes);
			while (cN == 0) {
				cN = r.nextInt(numNodes);
			}
			TreeBin t1 = c[0].getTree();
			TreeBin t2 = c[1].getTree();
			TreeBin subTree1 = t1.searchNode(cN).clone();
			TreeBin subTree2 = t2.searchNode(cN).clone();
			t1.sustitute(cN, subTree2);
			t2.sustitute(cN, subTree1);
		}
	}

	private ArrayList<Chromosome> generateRandomPopulation() {
		ArrayList<Chromosome> list = new ArrayList<Chromosome>(population);
		for (int chromosome = 0; chromosome < population; chromosome++) {
			add(list, new Chromosome());
		}
		return list;
	}

	private void init(ArrayList<Chromosome> list, boolean[] mask, int index1,
			int index2, Chromosome[] child) {
		// Mark the selected
		mask[index1] = mask[index2] = true;
		// Take the selected
		child[0] = list.get(index1);
		child[1] = list.get(index2);
		// Subtract the fitness from the total
		totalFitness -= child[0].getFitness();
		totalFitness -= child[1].getFitness();
	}

	private void reproduction(ArrayList<Chromosome> list) {
		int i = 0;
		boolean[] mask = new boolean[list.size()];
		Random random = new Random();
		while (i < list.size() - 1) {
			int index1 = random.nextInt(list.size());
			while (!mask[index1]) {
				int index2 = random.nextInt(list.size());
				if (index1 != index2 && !mask[index2]) {
					Chromosome[] child = new Chromosome[2];
					init(list, mask, index1, index2, child);
					crossover(child);
					child[0].mutate(mutation);
					child[1].mutate(mutation);
					add(chromosomes, child);
					i += 2;
				}
			}
		}
		if (list.size() % 2 == 1) {
			boolean found = false;
			for (int index = 0; !found && index < list.size(); index++) {
				if (found = !mask[index]) {
					add(chromosomes, list.get(index));
				}
			}
		}
	}

	private void reproductionElite(ArrayList<Chromosome> list) {
		int i = 0;
		boolean[] mask = new boolean[list.size()];
		Random random = new Random();
		while (i < list.size() - 1) {
			int index1 = random.nextInt(list.size());
			while (!mask[index1]) {
				int index2 = random.nextInt(list.size());
				if (index1 != index2 && !mask[index2]) {
					Chromosome[] child = new Chromosome[2];
					Chromosome parent1 = (Chromosome) list.get(index1).clone();
					Chromosome parent2 = (Chromosome) list.get(index2).clone();
					init(list, mask, index1, index2, child);
					crossover(child);
					child[0].mutate(mutation);
					child[1].mutate(mutation);
					child[0].evaluate();
					child[1].evaluate();
					double pf1 = parent1.getFitness();
					double pf2 = parent2.getFitness();
					double cf1 = child[0].getFitness();
					double cf2 = child[1].getFitness();
					if (pf1 >= pf2 && pf1 >= cf1 && pf1 >= cf2) {
						add(chromosomes, parent1);
						if (pf2 >= cf1 && pf2 >= cf2) {
							add(chromosomes, parent2);
						} else if (cf1 >= cf2) {
							add(chromosomes, child[0]);
						} else {
							add(chromosomes, child[1]);
						}
					} else if (pf2 >= cf1 && pf2 >= cf2) {
						add(chromosomes, parent2);
						if (pf1 >= cf1 && pf1 >= cf2) {
							add(chromosomes, parent1);
						} else if (cf1 >= cf2) {
							add(chromosomes, child[0]);
						} else {
							add(chromosomes, child[1]);
						}
					} else if (cf1 >= cf2) {
						add(chromosomes, child[0]);
						if (pf1 >= pf2 && pf1 >= cf2) {
							add(chromosomes, parent1);
						} else if (pf2 >= cf2) {
							add(chromosomes, parent2);
						} else {
							add(chromosomes, child[1]);
						}
					} else {
						add(chromosomes, child[1]);
						if (pf1 >= pf2 && pf1 >= cf1) {
							add(chromosomes, parent1);
						} else if (pf2 >= cf1) {
							add(chromosomes, parent2);
						} else {
							add(chromosomes, child[0]);
						}
					}
					i += 2;
				}
			}
		}
		if (list.size() % 2 == 1) {
			boolean found = false;
			for (int index = 0; !found && index < list.size(); index++) {
				if (found = !mask[index]) {
					add(chromosomes, list.get(index));
				}
			}
		}
	}

	private ArrayList<Chromosome> selection() {
		ArrayList<Chromosome> list = null;
		switch (typeSelection) {
		case TOURNAMENT:
			list = selectTournament();
			break;
		default:
			list = selectRoulette();
			break;
		}
		return list;
	}

	private ArrayList<Chromosome> selectRoulette() {
		ArrayList<Chromosome> list = new ArrayList<Chromosome>(n);
		int k = 0;
		double pX = x > 0 ? chromosomes.get(x - 1).getpAccumulated() : 0.0;
		while (k < n) {
			double p = new Random().nextDouble();
			if (p <= pX) {
				continue;
			}
			int index = binarySearch2(chromosomes, p);
			if (index == chromosomes.size()) {
				index--;
			}
			add(list, chromosomes.remove(index));
			k++;
		}
		return list;
	}

	private ArrayList<Chromosome> selectTournament() {
		ArrayList<Chromosome> list = new ArrayList<Chromosome>(k);
		for (int time = 0; time < k; time++) {
			ArrayList<Chromosome> tournament = new ArrayList<Chromosome>(z);
			int i = 0;
			while (i < z && chromosomes.size() > x) {
				int index = new Random().nextInt(chromosomes.size());
				if (x <= index) {
					add(tournament, chromosomes.get(index));
					chromosomes.remove(index);
					i++;
				}
			}
			add(list, tournament.get(0));
			tournament.remove(0);
			for (Chromosome c : tournament) {
				add(chromosomes, c);
			}
		}
		return list;
	}

	private void updateProbabilities() {
		Chromosome c = chromosomes.get(0);
		c.setpSelection(c.getFitness() / totalFitness);
		c.setpAccumulated(c.getpSelection());
		for (int i = 1; i < chromosomes.size() - 1; i++) {
			c = chromosomes.get(i);
			double pSelection = c.getFitness() / totalFitness;
			c.setpSelection(pSelection);
			c.setpAccumulated(pSelection
					+ chromosomes.get(i - 1).getpAccumulated());
		}
		c = chromosomes.get(chromosomes.size() - 1);
		c.setpSelection(c.getFitness() / totalFitness);
		c.setpAccumulated(1.0);
	}

	private void updateProbabilitiesRanking() {
		// P = 2 - PresionSelectiva + 2(PS - 1) * (pos - 1) / (tot - 1)
		int i = 0;
		double ps = 2.0;
		double prob;
		for (Chromosome c : chromosomes) {
			prob = 2 - ps + 2 * (ps - 1) * ((i - 1) / (population - 1));
			c.setpSelection(prob);
			i++;
		}
	}

	private void updateProbabilitiesStochastic() {
		// P = 2 - PresionSelectiva + 2(PS - 1) * (pos - 1) / (tot - 1)
		double pAcum = 1.0;
		double prob = 1 / population;
		for (Chromosome c : chromosomes) {
			c.setpSelection(prob);
			pAcum += prob;
			c.setpAccumulated(pAcum);
		}
	}

}
